package ua.yandex.collections;

import java.util.Comparator;

public class MyCollections {

    // Reverses the order of the elements in the specified list
    public static void reverse(MyList list) {
        int listSize = list.size();
        for (int i = 0; i < listSize / 2; i++) {
            Object element = list.get(i);
            list.set(i, list.get(listSize - 1 - i));
            list.set(listSize - 1 - i, element);
        }
    }

    //Реализует рекурсивный поиск в отсортированном массиве методом бисекции.
    public static int binarySearch(MyList list, Object key) {
        return binarySearch(list, key, 0, list.size() - 1);

    }

    //Реализует рекурсивный поиск в отсортированном массиве методом бисекции.
    public static int binarySearch(MyList list, Object key, Comparator cp) {

        return binarySearch(list, key, cp, 0, list.size() - 1);
    }

    private static int binarySearch(MyList list,
                                    Object key,
                                    int left,
                                    int right) {

        int middle = (left + right) / 2;
        int index = 0;
        if (((Comparable) key).compareTo(list.get(middle)) == 0) {
            index = middle;
        } else {
            if (left == right) {
                index = -middle - 1;
            } else {
                if (((Comparable) key).compareTo(list.get(middle)) < 0) {
                    return binarySearch(list, key, left, middle - 1);
                } else {
                    return binarySearch(list, key, middle + 1, right);
                }
            }
        }
        return index;
    }

    private static int binarySearch(MyList list,
                                    Object key,
                                    Comparator cp,
                                    int left,
                                    int right) {

        int middle = (left + right) / 2;
        int index = 0;
        if (cp.compare(key, list.get(middle)) == 0) {
            index = middle;
        } else {
            if (left == right) {
                index = -middle - 1;
            } else {
                if (cp.compare(key, list.get(middle)) < 0) {
                    return binarySearch(list, key, cp, left, middle - 1);
                } else {
                    return binarySearch(list, key, cp, middle + 1, right);
                }
            }
        }
        return index;
    }
}
